《统计学习方法》 第二章 学习笔记

感知机 —— 入门垫脚石，后续学的很多的算法都是在改进感知机的缺陷

知识树：

1、直观介绍：

红豆和绿豆的故事

超平面的划分

感知机模型的导入

2、感知机学习策略

函数问题

几何间隔

超平面的构造

3、感知机的学习算法

原始形式

算法收敛性

对偶形式

1、引入

划分红豆和绿豆

怎样的线是好的、怎样的线是不好的？

如果一条直线能够部分错一个点，那就是一条好的直线

如何量化直线有多好？

如果找不到好的直线呢？那就要在差的线里找到一条相对好的线

进一步，如果我们把所有分错的点和直线的距离求和，让这段求和的距离最小，这条直线就是我们要找的

总结以上：

1、一条直线不分错一个点，这就是好的直线

2、模型要尽可能找到好的直线

3、如果没有好的直线，在差的直线中找到较好的直线

4、判断直线多差的方式：分错的点到直线的距离求和。

感知机模型 f(x) = sign(wx+b)

sign(x) = \begin{cases} +1 , & x≥0 \\ -1 , & x-y_i(wx_i+b)>0

误分类点 x_i 到超平面S的距离为:( M 为误分类点集合) -\frac{1}{\lVert \boldsymbol w \rVert} \sum \limits_{x_i \in M}y_i(\boldsymbol w \cdot x_i+\boldsymbol b) 因为感知机是误分类驱动的，它的目标是不分错任何一个点，是将loss变为0，而不是找最优解，所以在梯度下降计算的时候，目标函数用的是函数间隔。

1、任取超平面 w_0, b_0

2、采用梯度下降法极小化目标函数 L(w,b) = - \sum \limits_{x_i \in M}y_i(\boldsymbol w \cdot x_i + \boldsymbol b) \\ \nabla_w L(w,b) = - \sum \limits_{x_i \in M}y_ix_i \\ \nabla_b L(w,b) = - \sum \limits_{x_i \in M}y_i \\

3、更新w, b w \leftarrow w+ \eta y_i x_i \\ b \leftarrow b + \eta y_i \\

总结：

1、感知机通过构造超平面的形式划分不同类的点

2、感知机属于线性判别模型，因为它的判别边界是线性的。

3、函数间隔和几何间隔的区别（感知机用的是函数间隔，因为它是误分类驱动）

解决当前问题的另一种方法，最后达到的目的是一样的

算法的原始形式

$\alpha_i$ 是第i个样本点，在整个训练过程中，被误分类的次数

总结：

1、感知机原始形式

2、原始形式到对偶形式的转换：转换为求解系数

3、对偶形式的意义；简化了运算过程

理论上证明感知机是有效的，

感知机是误分类驱动的，我们希望感知机最后是没有误分类的

所以要证明误分类次数K是有上限的。

需要通过证明有效性，从而知道在什么条件下，感知机可以达到比较好的效果

需要证明，感知机学习算法的原始形式在线性可分数据集上收敛。

便于推导，将偏置 b 并入权重向量 w ，记作 \tilde w=(w^T, b)^T ，同样也将输入向量加以扩充，加进常数1，记作 \tilde x=(x^T,1)^T ，显然，经过处理后， \tilde w \cdot \tilde x=w \cdot x+b

这样做过处理后，只是为了看起来简洁一些，并且便于做公式推导，其实展开来看，还是$w \cdot x+b$

结论：

设训练数据集 T={(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)} 是线性可分的，

其中 $ x_i \in X = R^n, y_i \in Y = {-1, +1}, i=1,2,...,N, 则

(1) 存在满足条件 \lVert \hat w_{opt}\rVert = 1 的超平面 \hat w_{opt} \cdot \hat x = w_{opt} \cdot x + b_{opt} = 0 将训练数据集完全正确分开；且存在 \gamma > 0 ， 对所有 i=1, 2, ... , N:

y_i ( \hat w_{opt} \cdot \hat x_i) = y_i(w_{opt} \cdot x_i + b_{opt}) \geq \gamma

样本点到超平面的距离是大于等于 \gamma

(2) 令 R=\underset{1 \leq i \leq N}{max} \lVert \hat x_i \rVert ，则感知机算法在训练数据集上的误分类次数k满足不等式：

k \leq (\frac{R}{\gamma})^2

R等于所有二范数里最大的那个，误分类次数K是小于等于 (\frac{R}{\gamma})^2

证明(1)

由于训练数据集是线性可分的，按照定义2.2，存在超平面可将训练数据集完全正确分开，取此超平面为 \hat w_{opt} \cdot \hat x = w_{opt} \cdot x + b_{opt} = 0，使 \lVert \hat w_{opt}\rVert = 1 。对所有的训练数据 i=1,2,...,N 均有：(不等式大于零说明该样本点没有被误分类，不等式小于等于零，说明该样本点被误分类了) y_i(\hat w_{opt} \cdot \hat x_i) = y_i(w_{opt} \cdot x_i + b_{opt}) > 0 所以存在 \gamma = min\{y_i(w_{opt} \cdot x_i + b_{opt})\} 使得 y_i(\hat w_{opt} \cdot \hat x_i) = y_i(w_{opt} \cdot x_i + b_{opt}) \geq \gamma

(2) 感知机算法从 \hat w = 0 开始，如果实例被误分类，则更新权重，令 \hat w_{k-1} 是第k个误分类实例之前的扩充权重向量，即 \hat w_{k-1} = (w_{k-1}^{T}, b_k-1)^T 则第k个误分类实例的条件是 y_i(\hat w_{k-1} \cdot \hat x_i) = y_i(w_{k-1} \cdot x_i + b_{k-1}) \leq 0 若 (x_i, y_i) 是被 \hat w_{k-1} = (w_{k-1}^{T}, b_{k-1})^T误分类的数据，则 w 和 b 的更新是 w_k \leftarrow w_{k-1} + \eta y_i x_i \\ b_k \leftarrow b_{k-1} + \eta y_i \\ \text 即 \hat w_k = \hat w_{k-1} + \eta y_i \hat x_i

总结：

1、通过证明感知机误分类次数是有上界的，说明通过有限次搜索可以找到将数据集完全正确分开的分离超平面。

2、当数据集线性不可分时，感知机学习算法不收敛，会发生振荡。